/***
 * 并查集Version5
 */
public class UnionFind5 implements UF{
    private int[] parent;
    private int[] rank;
    public UnionFind5(int size){
        parent = new int[size];
        for(int i=0;i<size;i++){
            parent[i] = i;
            rank[i] = 1;
        }
    }
    @Override
    public int getSize() {
        return parent.length;
    }

    /***
     * 查找index元素对应的根节点
     * @param index
     * @return
     */
    private int find(int index){
        if(index < 0 || index >= parent.length){
            throw new IllegalArgumentException("index is out of bound");
        }
        while(parent[index] != index){
            //每次将某元素的父亲指向改为该元素父亲的父亲以减小深度
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
    @Override
    public boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pIndex = find(p);
        int qIndex = find(q);
        if(pIndex == qIndex){
            return;
        }
        if(rank[pIndex] < rank[qIndex]){
            parent[pIndex] = qIndex;
        }else if(rank[qIndex] < rank[pIndex]){
            parent[qIndex] = pIndex;
        }else{
            parent[qIndex] = pIndex;
            rank[pIndex] ++;
        }
    }
}
